package leetCode.q206;

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    LinkedHashMap<Object,Object> map = null;
    Map.Entry<Integer,Integer>  d = null;

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //重新制作一个
    public ListNode reverseList(ListNode head) {
        ListNode ans = null;
        for (ListNode x = head; x != null; x = x.next) {
            //ans 前加一个结点
            ans = new ListNode(x.val, ans);
        }
        return ans;
    }

    //递归
    public ListNode reverseList1(ListNode head) {
        if(head == null||head.next == null){
            return head;
        }

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    class Solution1 {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next;

                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    }
}
